package com.yanceysong.codetop.s51_s60;

public class S54_Mid_43_字符串相乘 {
    /**
     * .S54_Mid_43_字符串相乘
     * .<p>
     * .LeetCode 链接：<a href="https://leetcode.cn/problems/multiply-strings/">https://leetcode.cn/problems/multiply-strings/</a>
     * .<p>
     * .题目描述：
     * .给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，乘积也用字符串表示。
     * .不允许使用任何内置的 BigInteger 库，也不能直接将输入转换为整数（即不能使用类似 Long.parseLong 直接得到数值再相乘）。
     * .<p>
     * .关键约束：
     * .1. 1 <= num1.length, num2.length <= 200
     * .2. num1 和 num2 仅由数字字符组成，且不包含前导零（除了数字 0 本身）
     * .3. 结果不会包含前导零（除了结果为 "0"）
     * .<p>
     * .核心标签：
     * .- 字符串处理
     * .- 模拟 / 数学
     * .- 数组
     * .<p>
     * .示例：
     * .输入：num1 = "2", num2 = "3"  输出："6"
     * .输入：num1 = "123", num2 = "456"  输出："56088"
     * .输入：num1 = "999", num2 = "999"  输出："998001"
     * .输入：num1 = "0", num2 = "456"  输出："0"
     * .输入：num1 = "100", num2 = "1000" 输出："100000" (尾部零处理正确)
     * .<p>
     * .解题思路（模拟「竖式乘法」）：
     * .传统手算乘法：逐位相乘后按位数（进位偏移）累加，再统一处理进位。
     * .例如：123 × 456
     * . = 123 × (400 + 50 + 6)
     * . = 123×6 + 123×50 + 123×400
     * . = 738 + 6150 + 49200
     * . = 56088
     * .我们用一个长度为 len1 + len2 的数组保存每一位的“累积和”（尚未完全进位处理），因为最大位数之和不会超过 len1 + len2。
     * .<p>
     * .核心操作：
     * .- 从最低位开始（右到左）遍历 num1 和 num2
     * .- 对于 num1[i] 与 num2[j] 的乘积 p，累加到数组的索引 position = i + j + 1
     * .  （为什么 +1：腾出最前面一位用于最终可能出现的进位）
     * .- 完成所有小乘法累加后，从数组末尾向前处理进位
     * .- 跳过前导零，拼接剩余数字形成结果字符串
     * .<p>
     * .ASCII 图解：
     * .假设 num1 = "123", num2 = "456"
     * . i j 遍历相乘：
     * .          1   2   3   (num1)
     * .          4   5   6   (num2)
     * .乘积位置索引映射（结果数组长度=3+3=6，下标0..5）
     * .num1[2] * num2[2] (=3*6=18) -> ans[5]
     * .num1[2] * num2[1] (=3*5=15) -> ans[4]
     * .num1[2] * num2[0] (=3*4=12) -> ans[3]
     * .num1[1] * num2[2] (=2*6=12) -> ans[4] 累加 (原15+12=27)
     * .num1[1] * num2[1] (=2*5=10) -> ans[3] 累加 (原12+10=22)
     * .num1[1] * num2[0] (=2*4=8)  -> ans[2]
     * .num1[0] * num2[2] (=1*6=6)  -> ans[3] 累加 (原22+6=28)
     * .num1[0] * num2[1] (=1*5=5)  -> ans[2] 累加 (原8+5=13)
     * .num1[0] * num2[0] (=1*4=4)  -> ans[1]
     * .初步数组(未进位处理完整)：[0,4,13,28,27,18]
     * .逐位自右向左做进位：
     * .ans[5]=18 -> 写8, 向ans[4]+=1  => ans[4]=28
     * .ans[4]=28 -> 写8, 向ans[3]+=2  => ans[3]=30
     * .ans[3]=30 -> 写0, 向ans[2]+=3  => ans[2]=16
     * .ans[2]=16 -> 写6, 向ans[1]+=1  => ans[1]=5
     * .ans[1]=5  -> 写5, 向ans[0]+=0
     * .ans[0]=0  -> 写0（可能是前导零，稍后丢弃）
     * .最终数组： [0,5,6,0,8,8] -> 去掉前导零 -> "56088"
     * .<p>
     * .关键洞察 / 易错点：
     * .1. 结果数组长度固定为 len1 + len2，避免后续扩容
     * .2. 相乘后的位置是 i + j + 1（不是 i + j），留出最前一位做统一进位
     * .3. 进位处理要自右向左，否则会产生连锁错误
     * .4. 处理完进位后可能出现前导零，需要跳过
     * .5. 输入若有一个是 "0"，可以直接返回 "0"（提前剪枝）
     * .<p>
     * .时间复杂度：O(len1 * .len2) —— 双重循环做逐位乘法
     * .空间复杂度：O(len1 + len2) —— 用数组保存结果的每一位
     * .<p>
     * .可选优化：
     * .- 若检测到较多的零位，可跳过乘法（例如某位为 '0' 时直接 continue）
     * .- 不推荐用字符串拼接逐步构建（效率较低），使用数组统一处理再构建结果
     */
    public String multiply(String num1, String num2) {
        // 去除可能的前导零（题目保证无，但做鲁棒性处理）
        num1 = stripLeadingZeros(num1);
        num2 = stripLeadingZeros(num2);
        // 快速返回：只要有一个操作数是 "0"，结果就是 "0"。
        if ("0".equals(num1) || "0".equals(num2)) {
            return "0";
        }
        // 获取两个字符串的长度
        int len1 = num1.length();
        int len2 = num2.length();
        // 结果最多 len1 + len2 位，使用整型数组保存每一位的累积和
        int[] productDigits = new int[len1 + len2];

        // 从右向左遍历两个字符串的每一位，模拟手算乘法
        for (int i = len1 - 1; i >= 0; i--) {
            int digit1 = num1.charAt(i) - '0'; // 当前 num1 的数字
            for (int j = len2 - 1; j >= 0; j--) {
                int digit2 = num2.charAt(j) - '0'; // 当前 num2 的数字
                // 乘积累加到对应位置 (i + j + 1)
                productDigits[i + j + 1] += digit1 * digit2;
            }
        }

        // 统一自右向左处理进位。这样不会遗漏连锁进位。
        for (int k = productDigits.length - 1; k > 0; k--) {
            productDigits[k - 1] += productDigits[k] / 10; // 往更高一位传递进位
            productDigits[k] %= 10;                       // 当前位只保留个位
        }

        // 跳过可能存在的前导零（只有 productDigits[0] 可能是 0）
        int startIndex = productDigits[0] == 0 ? 1 : 0;
        StringBuilder resultBuilder = new StringBuilder();
        for (int p = startIndex; p < productDigits.length; p++) {
            resultBuilder.append(productDigits[p]);
        }
        return resultBuilder.toString();
    }

    // --------------------- 测试代码区域（仿照环形链表题格式） ---------------------
    public static void main(String[] args) {
        S54_Mid_43_字符串相乘 solution = new S54_Mid_43_字符串相乘();
        System.out.println("=== 字符串相乘算法测试开始 ===\n");

        // 基础用例
        testSimpleCase(solution);
        testSmallSingleDigit(solution);
        testWithZeroOperand(solution);
        testBothZero(solution);

        // 进位与多位综合
        testClassicExample(solution);
        testAllNines(solution);
        testWithTailZeros(solution);

        // 边界场景
        testLeadingZeroInput(solution);
        testLargeNumbers(solution);
        randomStressTest(solution); // 可选的随机压力测试

        System.out.println("\n=== 所有测试完成 ===");
    }

    // 测试1: 最基础的乘法 2 * .3 = 6
    private static void testSimpleCase(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试1: 基础乘法 2 * .3 ---");
        String res = solution.multiply("2", "3");
        System.out.println("multiply(2,3) -> " + res + " (期望: 6)");
        assert "6".equals(res) : "基础乘法错误";
        System.out.println("✓ 基础乘法测试通过\n");
    }

    // 测试2: 单个小数字串 9 * .8 = 72
    private static void testSmallSingleDigit(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试2: 单数字串 9 * .8 ---");
        String res = solution.multiply("9", "8");
        System.out.println("multiply(9,8) -> " + res + " (期望: 72)");
        assert "72".equals(res) : "单数字串乘法错误";
        System.out.println("✓ 单数字串乘法测试通过\n");
    }

    // 测试3: 一个为0
    private static void testWithZeroOperand(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试3: 包含0 0 * .12345 ---");
        String res = solution.multiply("0", "12345");
        System.out.println("multiply(0,12345) -> " + res + " (期望: 0)");
        assert "0".equals(res) : "乘以0应为0";
        System.out.println("✓ 含0乘法测试通过\n");
    }

    // 测试4: 两个都为0
    private static void testBothZero(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试4: 双0 0 * .0 ---");
        String res = solution.multiply("0", "0");
        System.out.println("multiply(0,0) -> " + res + " (期望: 0)");
        assert "0".equals(res) : "双0乘法错误";
        System.out.println("✓ 双0乘法测试通过\n");
    }

    // 测试5: 题目经典示例 123 * .456 = 56088
    private static void testClassicExample(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试5: 经典示例 123 * 456 ---");
        String res = solution.multiply("123", "456");
        System.out.println("multiply(123,456) -> " + res + " (期望: 56088)");
        assert "56088".equals(res) : "经典示例错误";
        System.out.println("✓ 经典示例测试通过\n");
    }

    // 测试6: 全9乘法 999 * .999 = 998001
    private static void testAllNines(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试6: 全9乘法 999 * 999 ---");
        String res = solution.multiply("999", "999");
        System.out.println("multiply(999,999) -> " + res + " (期望: 998001)");
        assert "998001".equals(res) : "全9乘法错误";
        System.out.println("✓ 全9乘法测试通过\n");
    }

    // 测试7: 含尾部零 100 * .1000 = 100000
    private static void testWithTailZeros(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试7: 尾部零 100 * 1000 ---");
        String res = solution.multiply("100", "1000");
        System.out.println("multiply(100,1000) -> " + res + " (期望: 100000)");
        assert "100000".equals(res) : "尾部零处理错误";
        System.out.println("✓ 尾部零测试通过\n");
    }

    // 测试8: 输入含前导零（尽管题目保证不会出现，做鲁棒性验证） "0009" * ."0099" => "891" (9*99)
    private static void testLeadingZeroInput(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试8: 前导零输入 0009 * 0099 ---");
        String res = solution.multiply("0009", "0099");
        System.out.println("multiply(0009,0099) -> " + res + " (期望: 891)");
        assert "891".equals(res) : "前导零处理错误";
        System.out.println("✓ 前导零鲁棒性测试通过\n");
    }

    // 测试9: 较大的数字串（长度靠近边界）
    private static void testLargeNumbers(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试9: 大数字串乘法 ---");
        String num1 = repeatChar('9', 50); // 50位9
        String num2 = repeatChar('9', 50); // 50位9
        String res = solution.multiply(num1, num2);
        // 期望： (10^50 - 1)^2 = 10^100 - 2*10^50 + 1
        // 构造期望字符串："999...8000...0001" 形式
        String expected = buildSquareOfAllNines(50);
        System.out.println("长度校验 -> 结果长度:" + res.length() + " (期望: 100)");
        assert res.length() == 100 : "结果位数应为100";
        assert expected.equals(res) : "大数乘法结果不匹配";
        System.out.println("✓ 大数字串乘法测试通过\n");
    }

    // 测试10: 随机压力测试（与 Java 内置 BigInteger 对比，仅用于验证，不属于题解方式）
    private static void randomStressTest(S54_Mid_43_字符串相乘 solution) {
        System.out.println("--- 测试10: 随机压力测试 (少量用例) ---");
        java.util.Random rand = new java.util.Random(42); // 固定种子保证可复现
        for (int t = 1; t <= 10; t++) {
            int lenA = 1 + rand.nextInt(30); // 随机长度1~30
            int lenB = 1 + rand.nextInt(30);
            String a = randomNumericString(rand, lenA);
            String b = randomNumericString(rand, lenB);
            String prod = solution.multiply(a, b);
            // 用 BigInteger 校验正确性（只在测试使用）
            java.math.BigInteger bigA = new java.math.BigInteger(a);
            java.math.BigInteger bigB = new java.math.BigInteger(b);
            String expected = bigA.multiply(bigB).toString();
            assert expected.equals(prod) : "随机测试失败: " + a + " * ." + b + " => " + prod + " != " + expected;
        }
        System.out.println("✓ 随机压力测试全部通过\n");
    }

    // 辅助方法：重复某个字符 n 次
    private static String repeatChar(char c, int n) {
        return String.valueOf(c).repeat(Math.max(0, n));
    }

    // 构造 (10^n - 1)^2 的字符串结果：10^(2n) - 2*10^n + 1
    // 对于 n 位全9的数平方，模式：前 (n-1) 位递增到 (n-1)，中间若干 9/8/0 的组合，最后 1
    // 具体： 99^2 = 9801, 999^2 = 998001, 9999^2 = 99980001
    private static String buildSquareOfAllNines(int n) {
        // 正确模式：(10^n - 1)^2 = (n-1)个9 + 8 + (n-1)个0 + 1
        // 例：n=2 -> 9 8 0 1; n=3 -> 99 8 00 1; n=4 -> 999 8 000 1
        if (n == 1) {
            return "81"; // 9^2
        }
        return "9".repeat(Math.max(0, n - 1)) +
               '8' +
               "0".repeat(Math.max(0, n - 1)) +
               '1';
    }

    // 生成随机数字串（不含前导零，保证第一位不是0，除非长度为1）
    private static String randomNumericString(java.util.Random rand, int len) {
        StringBuilder sb = new StringBuilder(len);
        for (int i = 0; i < len; i++) {
            int d = rand.nextInt(10);
            if (i == 0 && len > 1 && d == 0) d = 1; // 避免前导零
            sb.append(d);
        }
        return sb.toString();
    }

    // 去除字符串 s 的前导零（保留一个零若全是零）
    private static String stripLeadingZeros(String s) {
        int i = 0;
        // 保留最后一个零若字符串全是零
        while (i < s.length() - 1 && s.charAt(i) == '0') {
            i++;
        }
        return s.substring(i);
    }
}
